%!TEX program = xelatex
\documentclass[lang=cn,11pt,a4paper]{elegantpaper}

% 标题区域
\title{一元二次方程实数域求根算法}
\author{强基数学2001 \\ 关博仁}
\date{\zhtoday}

% 本文档命令
\usepackage{array,url,subfigure,stfloats,tikz}
\usetikzlibrary{positioning, shapes.geometric, calc}
\usepackage[lined,boxed,commentsnumbered]{algorithm2e}
\newcommand{\ccr}[1]{\makecell{{\color{#1}\rule{1cm}{1cm}}}}
\newcommand{\code}[1]{\lstinline{#1}}

% 文档区
\begin{document}

% 建立标题
\maketitle

% 摘要
\begin{abstract}
本文为浙江大学2021-2022短学期王何宇老师的《数学软件》课程作业，本文将详细介绍二分法求解实数域上一元二次方程，并引入倍增法来提高效率。本次作业将会发布到仓库\href{https://gitee.com/wellsguan/mathematics-software/tree/master/Day7}{Gitee/Day7}中。
\keywords{二分法, 倍增, 一元二次方程求根}
\end{abstract}

% 问题介绍
\section{二次型的判别式}

任何的一元二次方程有以下形式
\[ax^2+bx+c, \quad a,b,c\in \mathbb{R}\]
简单配方得到
\[(x+\dfrac{b}{2a}) = \dfrac{b^2-4ac}{4a^2}\]
得到二次型的Delta判别式
\[\Delta = b^2-4ac\]
容易知道有
\begin{enumerate}
    \item $\Delta < 0$, 方程无实根
    \item $\Delta = 0$, 方程有两相同实根
    \item $\Delta > 0$, 方程有两不相同实根
\end{enumerate}
此处通过算法求根我们不使用求根公式，选择通过二分法来尝试能否得到更高精度的解。

% 算法分析
\section{算法流程}

\subsection{二分法}
    对于已知有$a,b$使得$f(a)f(b)<0$的条件，我们已经很熟悉如何用二分法求得方程的根，流程图如下:
    %% 流程图居中
    \begin{center}
        \begin{tikzpicture}[node distance=10pt]
            \node[draw, rounded corners]                        (start)   {初始化l,r,$\epsilon$};
            \node[draw, below=of start]                         (begin)   {mid=(l+r)/2};
            \node[draw, below=of begin]                         (step 1)  {判断 f(mid)=0};
            \node[draw, below=30pt of step 1]                   (step 2)  {判断 f(mid)与f(l)同号};
            \node[draw, right=30pt of step 2]                   (step 3)  {令l=mid};
            \node[draw, below=30pt of step 2]                   (step 3if){令r=mid};
            \node[draw, below=30pt of step 3]                   (judge)   {判断r-l是否<$\epsilon$};
            \node[draw, below=of step 3if]                      (end)     {输出mid};
            
            \draw[->, >= stealth] (start) -- (begin);
            \draw[->, >= stealth] (begin)  -- (step 1);
            \draw[->, >= stealth] (step 1) -- node[left] {No} (step 2);
            \draw[->, >= stealth] (step 2) -- node[above] {Yes} (step 3);
            \draw[->, >= stealth] (step 2) -- node[left] {f(mid)与f(r)同号} (step 3if);
            \draw[->, >= stealth] (step 3) -- (judge);
            \draw[->, >= stealth] (step 3if) -- (judge);
            \draw (step 1)--(-3.5,-1.9)-- node[left]{Yes}(-3.5,-6.3);
            \draw[->, >= stealth] (-3.5,-6.3)--(end);
            \draw[->, >=stealth] (judge)--(judge|-end)--node[above] {Yes} (end);
            \draw (judge)--($(judge)+(2,0)$)--node[left]{No} ($(judge)+(2,0)+(begin)-(step 3if)$);
            \draw[->, >= stealth] ($(judge)+(2,0)+(begin)-(step 3if)$)->(begin);
         
            \end{tikzpicture}
    \end{center}
    
    下面思考如何快速找到符合条件的两个点$a,b$。

\subsection{倍增法}
    很容易知道当方程有两个不同实根时，对于
    \[x = -\dfrac{b}{2a}\]
    有$f(x)<0$，并且函数图像关于$x = -\dfrac{b}{2a}$对称，因此以$x$为起始点做$d =  1$的倍增即可，得到算法流程图:
    % 流程图居中
    \begin{center}
        \begin{tikzpicture}[node distance=10pt]
            \node[draw, rounded corners]                        (start)   {初始化x,d};
            \node[draw, below=of start]                         (begin)   {判断f(x+d)>0};
            \node[draw, below=20pt of begin]                    (nope)    {d=2d,x=x+d};     
            \node[draw, right=40pt of begin]                    (end)     {对(x,x+d)与对称区间二分取得两个零点};
            
            \draw[->, >= stealth] (start) -- (begin);
            \draw[->, >= stealth] (begin) -- node[left] {No} (nope);
            \draw[->, >= stealth] (begin) -- node[above] {Yes} (end);
            \draw[->, >= stealth] (nope) -- ($(nope)+(0,-1)$) -- ($(nope)+(-2,-1)$) -- ($(begin)+(-2,0)$)--(begin);
            \end{tikzpicture}
    \end{center}
    
    \section{计算实例}
    以下是根据上述流程图编写的\code{C++}程序的运行结果, 源代码见仓库, 有根分布的以下三种情况，编译出\code{main}后，
    得到输出
    \begin{lstlisting}
    a: 3 b: -567 c: 89
    The error: 0.000000 0.000000
    0.158472 16.518
    a: 1 b: 0 c: 5
    The Quadratic equation has no real zero!
    0 0
    a: 1 b: -5 c: 6.25
    The error: 0.000000 0.000000
    2.5 2.5
    \end{lstlisting}
    \code{error}直接计算零点处函数值得到。
    用\code{gnuplot}作图得:
    \begin{figure}[htbp]
    \centering
    \subfigure[Fig.1]{\includegraphics[width=0.28\textwidth]{graph/output_1.jpg}}
    \subfigure[Fig.2]{\includegraphics[width=0.28\textwidth]{graph/output_2.jpg}}
    \subfigure[Fig.3]{\includegraphics[width=0.28\textwidth]{graph/output_3.jpg}}
    \label{fig:my_label}
    \end{figure}
    \newline
    注意到三组数据分别有$\Delta >0, \Delta =0, \Delta <0$，与预期一致。
    
    \section{结论}
    二分法计算精度可观，与\code{gnuplot}作图结果相似，算法正确。
    
    \section{代码包说明}
    \code{make}: 生成可执行文件\code{bin/main}
    
    \code{make report}: 生成\code{report.pdf}与它所需要的图片
    
    \code{make clean}: 清除可执行文件与生成的图片
    
    \code{bash test \$a \$b \$c }: 可自定义测试， 生成输入的二次型图像并以\code{test.jpg}格式保存在当前目录\code{Day7}下 
    


\end{document}
